Au niveau fondamental, une liste chaînée est une structure de données récursive définie par son absence ou sa composition. Une liste est soit vide (représentée par []) soit elle est composée d'un Tête contenant une seule valeur et une Queue qui est elle-même une liste complète.

1. La définition récursive

En définissant la queue comme « elle-même une liste », nous permettons un emboîtement infini. Cela est illustré par la construction de [ 1 | [ 2 | [ 3 | [ ] ] ] ], où chaque opérateur de tuyau (|) sépare la valeur immédiate de la structure restante.

2. Primitif versus Abstraction

Les listes primitives dans la machine virtuelle Erlang (BEAM) sont des structures simples. Des comportements comme List.flatten/1 sont des abstractions fournies par le module List d'Elixir. La structure de données brute ne « sait » pas comment se déplier elle-même ; c'est le module qui fournit la logique pour parcourir les têtes et queues imbriquées.

3. L'analogie des poupées russes

Imaginez une liste chaînée comme un ensemble de poupées russes. La poupée externe est la Tête. Quand vous l'ouvrez, vous trouvez exactement une chose : une autre poupée (la Queue). Vous n'atteignez l'état Vide que lorsque vous ouvrez la dernière poupée, la plus petite, et que vous ne trouvez rien à l'intérieur.